iT邦幫忙

2025 iThome 鐵人賽

DAY 8
0

https://ithelp.ithome.com.tw/upload/images/20250922/20177944bbqvkFS5zR.jpg

範例一:[3,4,5,1,2]
l=0,r=4 → m=2,a[m]=5,a[r]=2 ⇒ a[m]>a[r] → l=3
l=3,r=4 → m=3,a[m]=1,a[r]=2 ⇒ a[m]≤a[r] → r=3
l==r==3,最小值=1

class Solution{//153 O(log n) O(1)
public:
    int findMin(vector<int>& a){ //旋轉升序陣列
        int l=0,r=(int)a.size()-1; //邊界
        while(l<r){ //至少兩個元素二分
            int m=(l+r)>>1; //中點
            if(a[m]<=a[r]) r=m; //右半已排,最小不在右半內,右界收至m
            else l=m+1; //否則最小在右半,左界m+1
        }
        return a[l]; //l==r最小值
    }
};

上一篇
Binary Search 3->4 & 補眠日QQ
下一篇
Binary Search 5->6 手機發文有難度 & 明天來準備周四簡報囉
系列文
轉職仔之Data Science and ai master後的持續精進技術之路10
圖片
  熱門推薦
圖片
{{ item.channelVendor }} | {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

1 則留言

1
AndyAWD
iT邦新手 2 級 ‧ 2025-09-22 22:28:29

明天沒颱風假,太傷心了

我要留言

立即登入留言